The present invention relates generally to routing of data through a communications network, and more specifically to a system and method for node and link insertion to provide deadlock-free routing on arbitrary topologies.
As it is generally known, routing is the process of determining the nodes through which a data unit is forwarded along its path between a source and a destination within a network. The route taken by data, such as a packet or other specific type of data unit, is also referred to herein as the path taken between the source and destination. Routing is performed by various kinds of data forwarding devices, including routers and switches. A forwarding device that performs routing is typically connected to multiple communication links, and operates to select at least one of those communication links as an output link for each received data unit to be forwarded. Thus it is seen that routing in general is concerned with determining which paths are used for forwarding data units through a network.
Existing routing systems employ routing tables that define the routes to be taken between nodes within a network. An example of a routing table 10 is shown in FIG. 1. As shown in FIG. 1, the routing table 10 includes a number of rows 12 and a number of columns 14. Each of the rows 12 contains next hop forwarding information for a corresponding source node in the network. The routing table 10 includes routing information for N nodes. The row indices for the routing table 10 are thus associated with nodes making a forwarding decision (“source” nodes) regarding one or more data units they have received, and the column indices for the routing table 10 are associated with destination nodes to which those data units are addressed and ultimately delivered (“destination” nodes).
Information within a routing table entry having indices Row_Index and Column_Index describes how a node associated with Row_Index should forward a data unit addressed to a destination node associated with Column_Index. For example, considering a hypothetical network including a node X and a node Y, row R3 16 may be used to store forwarding information to be used by a corresponding node X. Accordingly, each entry in row R3 16 would contain forwarding information to be used when forwarding data units received by node X. Data units received by node X and having a destination address indicating node Y, for example, would be forwarded by node X based on forwarding information contained in a forwarding table entry located using a column index corresponding to node Y, shown for purposes of illustration as column index C2 18. As a result, as illustrated in FIG. 1, node X would reference the forwarding information contained in the routing table entry 20. Such forwarding information would, for example, indicate an outgoing link from node X onto which the received data unit should be forwarded, as well as any other information needed to forward the data unit to a next node along its path to node Y. Each forwarding table entry may further include information describing the cost of such a next hop defined by forwarding information within the entry. Such cost information may reflect distance, delay, or other costs associated with forwarding a received data unit according to the forwarding information within the routing table entry.
During operation of existing systems, the contents of each row within the routing table 10 are typically forwarded to its corresponding source node within the network. As described above, each row within the routing table 10 serves as a “forwarding table” for its corresponding node, providing the routing information needed by that node to forward the data units it receives. As illustrated in FIG. 1, row R3 16 would therefore be forwarded to node X, to serve as the forwarding table for node X.
Generation of a complete routing table such as the routing table 10 in FIG. 1, and distribution of the rows within the routing table as forwarding tables to nodes within the network, are costly procedures which consume valuable resources and may adversely impact network performance. When a new node is added to a network, it is desirable to make as few changes to the routing table as possible, in order to minimize the forwarding tables (rows) that need to be transmitted over the network.
Traditional routing systems have also attempted to compute paths that do not contain loops. However, even where loop-free paths have been determined, traffic flows can interact with each other to cause a problem known as “deadlock” within the network. For example, deadlock can occur within a group of switches, each of which has buffers full of received data, and cannot drop any packet from its buffer. Each of the switches in such a group may be unable to forward its received data because the switch to which that data must be forwarded has no available buffers in which to store the data.
FIG. 2 illustrates the occurrence of deadlock in a group of four switches, referred to as nodes, within a communication network. The nodes 30, 34, 38 and 42 of FIG. 1 each include buffers for storing data, and may be interconnected using any conventional type of communication links or media. The data flows 32, 36, 40 and 44 consist of data units passed over such communication links between the nodes 30, 34, 38 and 42.
In the scenario illustrated in FIG. 2, node 30's buffers are filled with packets received from a data flow 32. However, node 30 cannot forward the packets it has received to node 34, since node 34's buffers are filled with packets from a data flow 36 that node 34 can't forward to node 38, since node 38's buffers are filled with packets from data flow 40. Similarly, node 38 cannot forward its data to node 42, since node 42's buffers are also filled. FIG. 2 thus illustrates how the occurrence of deadlock in a network can result in significant network performance problems.
Existing routing systems have been developed which provide deadlock-free sets of paths by either constraining the topology of the network itself, and/or by constraining the routes which may be taken through the network. For example, the topology of a network may be constrained such that the network topology is arranged as a grid. Given a grid topology, if all paths through the network are required to first traverse links horizontally as far as necessary, then vertically to the destination node, the network will be deadlock-free. Also, if the network topology is a tree, which by definition includes no loops, then the network will be deadlock-free during operation.
Existing systems have employed centralized techniques to compute deadlock-free sets of paths. A centralized approach operates such that one node obtains the complete topology of the network, for example by having each other node in the network report which neighbor nodes it is connected to. The central node then calculates a set of deadlock-free paths for the entire network, and stores them within a routing table. Once computed, these paths can then be distributed in forwarding tables to all other nodes, thus informing each node in the network which neighbor node to forward a received data unit to, for each potential destination within the network.
One existing approach to determining paths through a network is known as “up/down routing.” In up/down routing, one of the nodes in the network is chosen arbitrarily as the root of a spanning tree for the network. All links within the network are then designated as “up” or “down” links with respect to the root node. The determination of an “up” or “down” state for a given link is based on the position of the link with respect to the spanning tree. A link is “up” if it points from a lower to a higher level node in the tree. Otherwise, the link is considered a “down” link. For nodes at the same level, node IDs are used to break the tie. Routing of packets from a source to a destination is performed such that any “up” links (towards the root) in the path are traversed before any “down” links are traversed (away from the root) in order to reach the destination. Accordingly, once a “down” link has been traversed, no “up” links may be used within that path. This approach produces routes that are deadlock-free. However, a significant problem with up/down routing is that a disproportionate amount of traffic may be directed through links connected to the root node.
For these reasons it would be desirable to have an efficient system for inserting routing information for a new node and/or link into a routing table, where the routing table reflects a set of deadlock-free routes for the network. The system should minimize the impact of adding a new node or link to the network in terms of modifications to the routing table, and the distribution of forwarding tables to nodes within the network. The system should further operate to maintain the deadlock-free quality of routes defined by forwarding information stored in the routing table.